// 斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列。
// 该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

// F(0) = 0，F(1) = 1
// F(n) = F(n - 1) + F(n - 2)，其中 n > 1

const fib = function (n: number): number {
    let dp1: number = 0; // 代表F(n - 2)
    let dp2: number = 1; // 代表f(n - 1)
    // 安全检测
    if (n === 0 || n === 1) return n;
    let curr: number = 1;
    // 条件转移方程
    while (curr < n) {
        let originDp1: number = dp1;
        dp1 = dp2;
        dp2 = originDp1 + dp2;
        curr++;
    }
    return dp2;
};


// 这道题不用多说，动态规划和递归算法经典性质的入门例题了
// 这里只给出动态规划算法的解法，这里声明两个变量dp
// dp1代表代表F(n - 2)，dp2代表f(n - 1)
// 之后每一轮状态转移方程其实就非常好写出来了
// 我们将旧dp1储存，新的dp1其实应该是旧的dp2（往前递推一步）
// 而新的dp2应该是旧的dp1 + 旧的dp2
// 状态转移方程写出后这道题也就迎刃而解了。